{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structures - Linked Lists\n",
    "\n",
    "A linked list is a sequence of individual data elements called Nodes, which are connected via links. Each data element contains a connection to another data element in the form of a pointer. Visually we can think of a node like the following:\n",
    "\n",
    "<img src=\"LinkedLists - Node.png\" width=\"300\">\n",
    "\n",
    "A collection of nodes is called a list, and can be visualized as the following:\n",
    "\n",
    "<img src=\"LinkedList - List.png\" width=\"500\">\n",
    "\n",
    "The first node is a particular node that we call the head, or in other words, it is the first chain in the link of nodes.\n",
    "\n",
    "### Advantages\n",
    "1. Linked Lists are dynamic, meaning it can grow and shrink at runtime by allocating and deallocating memory. Meaning there is no requirement to give the initial size of the list.\n",
    "\n",
    "2. Insertion and deletion operations are more natural than with arrays. We don't have to shift nodes like array insertion. In Insertion operation in a linked list, we have to update the next link of the node.\n",
    "\n",
    "3. It doesn't waste memory, meaning that it only takes the memory needed to store all nodes. On the other side, arrays can take up more memory than needed. For example, if we declare an array to store six values but only put four values in it, we are wasting the remaining two place holders in memory. To be clear, this does not mean a linked list uses less memory; it just means it uses the memory efficiently.\n",
    "\n",
    "## Why Use Linked Lists\n",
    "\n",
    "Often linked lists will be compared to arrays, but different features allow linked lists to stand out from normal arrays.\n",
    "\n",
    "### Disadvantages\n",
    "1. Accessing a node is time-consuming. When looking for a value in a linked list, you have to start from the beginning of the chain and check one element at a time for the value you're looking for. If the linked list is n elements long, this can take **up to n time**.\n",
    "\n",
    "2. It takes up more memory than an array. This is because it contains a pointer to the next node, with an array we don't have the pointer because it is stored in memory sequentially.\n",
    "\n",
    "## Performance\n",
    "\n",
    "| Data Structure | Average Insert | Average Delete | Average Search | Worst Insert | Worst Delete | Worst Search |\n",
    "|----------------|----------------|----------------|----------------|--------------|--------------|--------------|\n",
    "| Linked List    | O(1)           | O(1)           | O(n)           | O(1)         | O(1)         | O(n)         |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the basis of a linked list is the node object. A linked list can be made up of multiple nodes.\n",
    "# we need our node to do a couple of things, return the data inside it, get the node next to it if there is one and \n",
    "# set the node next to it\n",
    "\n",
    "class Node(object):\n",
    "\n",
    "    # every node starts off with a piece of data, and we define the node next to it.\n",
    "    def __init__(self, data=None, next_node=None):\n",
    "        self.data = data\n",
    "        self.next_node = next_node\n",
    "\n",
    "        \n",
    "    # this will return the data in the current node we are on.\n",
    "    def get_data(self):\n",
    "        return self.data\n",
    "    \n",
    "\n",
    "    # this grabs the next node.\n",
    "    def get_next(self):\n",
    "        return self.next_node\n",
    "    \n",
    "\n",
    "    # this sets the next node.\n",
    "    def set_next(self, new_next):\n",
    "        self.next_node = new_next\n",
    "\n",
    "\n",
    "        \n",
    "class LinkedList(object):\n",
    "    \n",
    "    def __init__(self, head = None, end = None):        \n",
    "        self.head = head\n",
    "        self.end = end\n",
    "        \n",
    "        \n",
    "    def insert_front(self, data):\n",
    "        '''\n",
    "            Insert a node at the beginning of our list\n",
    "            Time Complexity: O(1) \n",
    "        '''\n",
    "        \n",
    "        # define a new node\n",
    "        new_node = Node(data)\n",
    "        \n",
    "        # the second node will be the old first one\n",
    "        new_node.set_next(self.head)\n",
    "        \n",
    "        # the new head will be the new node\n",
    "        self.head = new_node\n",
    "        \n",
    "        \n",
    "    def insert_end(self, data):        \n",
    "        '''\n",
    "            Insert a node at the end of our list.\n",
    "            Time Complexity: Θ(1) when last element is known,\n",
    "                             Θ(n) when last element is unknown\n",
    "        '''\n",
    "        \n",
    "        # define a new node and the head node\n",
    "        new_node = Node(data)\n",
    "        head_node = self.head\n",
    "        \n",
    "        # if there isn't a head node then the head node will be the last node\n",
    "        if head_node is None:\n",
    "            head_node = new_node\n",
    "            return\n",
    "        \n",
    "        # otherwise, let's find the last node\n",
    "        last_node = head_node\n",
    "\n",
    "        # as long as there is a \"next\" node that means we haven't reached the end\n",
    "        while last_node.get_next() != None:        \n",
    "            last_node = last_node.get_next()\n",
    "        \n",
    "        # when we have reached the end, set the next node to the new node we created above.\n",
    "        last_node.set_next(new_node)\n",
    "        self.end = new_node\n",
    "        \n",
    "        \n",
    "    def insert_middle(self, middle_node, data):\n",
    "        '''\n",
    "            Insert a node in the middle of our list\n",
    "            Time Complexity: search time + Θ(1) \n",
    "        '''        \n",
    "        \n",
    "        if middle_node is None:\n",
    "            print(\"The node you've selected does not exist.\")\n",
    "        \n",
    "        new_node = Node(data)\n",
    "        new_node.set_next(middle_node.get_next())\n",
    "        middle_node.set_next(new_node)\n",
    "        \n",
    "        \n",
    "    def list_size(self):\n",
    "        '''\n",
    "            Return the list size\n",
    "            Time Complexity: O(n) \n",
    "        '''\n",
    "        \n",
    "        current_node = self.head        \n",
    "        current_count = 0\n",
    "        \n",
    "        while current_node:            \n",
    "            current_count += 1\n",
    "            current_node = current_node.get_next()\n",
    "            \n",
    "        return current_count\n",
    "    \n",
    "    \n",
    "    def search_list(self, value):\n",
    "        '''\n",
    "            Search the list and return all the nodes that contain a given value.\n",
    "            Time Complexity: O(n) \n",
    "        '''\n",
    "        \n",
    "        current_node = self.head\n",
    "        previous_node = None\n",
    "        result_list = []\n",
    "        \n",
    "        # if the head node is none, then we can just exit early.\n",
    "        if current_node == None:\n",
    "            return\n",
    "        \n",
    "        # if it's not none then start searching for the value.\n",
    "        # there are two conditions where we stop traversing the node.\n",
    "        # 1st. The current node is None, which means we've reached the end.\n",
    "        # 2nd. We found the value so we continue you on to deletion\n",
    "        while current_node != None:\n",
    "            \n",
    "            if current_node.data == value:                \n",
    "                result_list.append(current_node)\n",
    "                previous_node = current_node\n",
    "                current_node = current_node.get_next()   \n",
    "                \n",
    "            else:\n",
    "                previous_node = current_node\n",
    "                current_node = current_node.get_next()   \n",
    "\n",
    "        return result_list\n",
    "    \n",
    "\n",
    "    def delete_list(self): \n",
    "        '''\n",
    "            Delete the entire list itself.\n",
    "            Time Complexity: O(n) \n",
    "        '''\n",
    "        \n",
    "        # initialize the current node \n",
    "        current = self.head \n",
    "        \n",
    "        while current: \n",
    "            \n",
    "            # grab the next node\n",
    "            next_node = current.next_node \n",
    "              \n",
    "            # delete the current node \n",
    "            del current.data \n",
    "              \n",
    "            # set current equal to the next node \n",
    "            current = next_node \n",
    "            \n",
    "            \n",
    "    def delete_node(self, value):\n",
    "        '''\n",
    "            Delete the first instance of a value.\n",
    "            Time Complexity: O(1) when at beginning, \n",
    "                             O(1) when at end and element is known, \n",
    "                             O(n) when at end and element is unknown,\n",
    "                             search time + Θ(1) when in middle\n",
    "        '''\n",
    "        \n",
    "        current_node = self.head\n",
    "        found = False\n",
    "        previous_node = None\n",
    "        \n",
    "        # if the head node is none, then we can just exit early.\n",
    "        if current_node == None:\n",
    "            return\n",
    "        \n",
    "        # if it's not none then start searching for the value.\n",
    "        # there are two conditions where we stop traversing the node.\n",
    "        # 1st. The current node is None, which means we've reached the end.\n",
    "        # 2nd. We found the value so we continue you on to deletion\n",
    "        while current_node != None and found is False:\n",
    "            \n",
    "            if current_node.data == value:\n",
    "                found == True\n",
    "                break\n",
    "                \n",
    "            else:\n",
    "                previous_node = current_node\n",
    "                current_node = current_node.get_next() \n",
    "\n",
    "                \n",
    "        # if it wasn't found let the user know.\n",
    "        if current_node is None:\n",
    "            raise ValueError(\"Data not in list\")\n",
    "            \n",
    "        # if it was found then delete it.\n",
    "        if previous_node is None:\n",
    "            # if the head node contains the value, jump it and set the next node to be the head node.\n",
    "            self.head = current_node.get_next()\n",
    "        else:\n",
    "            # if isn't the head node then take the previous node and set it as the next node.\n",
    "            previous_node.set_next(current_node.get_next())\n",
    "\n",
    "        \n",
    "    def traverse(self):        \n",
    "        '''\n",
    "            Traverse the list and print each value.\n",
    "            Time Complexity: O(n)\n",
    "        '''\n",
    "        \n",
    "        # first define the node\n",
    "        node = self.head\n",
    "        \n",
    "        while node != None:\n",
    "            \n",
    "            # print the node and then set the new node equal to the next one.\n",
    "            # if the next one doesn't equal none (there is no value after it) then it\n",
    "            # will keep printing\n",
    "            print(node.get_data())\n",
    "            node = node.get_next()\n",
    "         \n",
    "        \n",
    "    def remove_duplicates(self):\n",
    "        '''\n",
    "            Remove duplicate values from the list.\n",
    "            Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).\n",
    "        '''\n",
    "        \n",
    "        # grab the first node and the node after the first\n",
    "        previousNode = self.head\n",
    "        currentNode = previousNode.next_node\n",
    "        \n",
    "        # build a set to store non-duplicate values\n",
    "        keys = set([previousNode.data])\n",
    "        \n",
    "        while currentNode:\n",
    "            \n",
    "            data = currentNode.data\n",
    "            \n",
    "            # if it is a duplicate\n",
    "            if data in keys:\n",
    "                \n",
    "                # have the previous node's next pointer by pass the current node and point to the node after it.\n",
    "                previousNode.next_node = currentNode.next_node\n",
    "                \n",
    "                # set up for the next run\n",
    "                currentNode = currentNode.next_node\n",
    "                \n",
    "            else:\n",
    "                \n",
    "                # else it was a unique value so add it to the set\n",
    "                keys.add(data)\n",
    "                \n",
    "                # reassign the nodes\n",
    "                previousNode = currentNode\n",
    "                currentNode = currentNode.next_node\n",
    "                \n",
    "            \n",
    "    def kth_to_last(self, k):\n",
    "        '''\n",
    "            Return kth to the last elements of our list.\n",
    "            Time Complexity: O(n) \n",
    "        '''        \n",
    "        \n",
    "        # if k is negative just return nothing\n",
    "        if k < 0:\n",
    "            return None\n",
    "        \n",
    "        # if k is 0 just print the whole list\n",
    "        if k == 0:\n",
    "            self.traverse()\n",
    "            return\n",
    "           \n",
    "        # grab the list length\n",
    "        list_length = self.list_size()\n",
    "            \n",
    "        # in the situaiton where they give us a K larger then the list length, pass back an error.\n",
    "        if k > list_length:\n",
    "            print(\"You chose a K which is longer than the list.\")\n",
    "        \n",
    "        # start from the beginning\n",
    "        p1 = self.head\n",
    "        \n",
    "        # go from position 1 to the end of the list\n",
    "        for i in range(1, list_length + 1):\n",
    "            if i >= k:\n",
    "                print(p1.data) \n",
    "                p1 = p1.next_node\n",
    "            else:\n",
    "                p1 = p1.next_node\n",
    "                \n",
    "                \n",
    "\n",
    "    def sum_linked_list(self, linked_list):\n",
    "        '''\n",
    "            Sum two individual linked lists.\n",
    "            Time Complexity: O(m + n) where m and n are number of nodes in first and second lists respectively.\n",
    "        '''\n",
    "        \n",
    "        # define the total\n",
    "        total = 0\n",
    "        \n",
    "        # grab the first node from each list\n",
    "        p1 = self.head\n",
    "        p2 = linked_list.head\n",
    "        \n",
    "        # sum all the value's from list 1\n",
    "        while p1:\n",
    "            if isinstance(p1.data,(int, float)):\n",
    "                total = total + p1.data\n",
    "                p1 = p1.get_next()\n",
    "            else:\n",
    "                p1 = p1.get_next()\n",
    "        \n",
    "        # sum all the value's from list 2\n",
    "        while p2:\n",
    "            if isinstance(p2.data,(int, float)):\n",
    "                total = total + p2.data\n",
    "                p2 = p2.get_next()\n",
    "            else:\n",
    "                p2 = p2.get_next()\n",
    "        \n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37\n",
      "37\n",
      "50\n",
      "35\n",
      "35\n",
      "90\n",
      "Bob\n",
      "35\n",
      "--------------------------------------------------\n",
      "37\n",
      "37\n",
      "50\n",
      "35\n",
      "35\n",
      "Bob\n",
      "35\n",
      "--------------------------------------------------\n",
      "37\n",
      "50\n",
      "35\n",
      "Bob\n",
      "35\n"
     ]
    }
   ],
   "source": [
    "# let's first define a linked list\n",
    "linked_list = LinkedList()\n",
    "linked_list2 = LinkedList()\n",
    "\n",
    "linked_list2.insert_front(35)\n",
    "linked_list2.insert_front(35)\n",
    "linked_list2.insert_front(37)\n",
    "linked_list2.insert_front(37)\n",
    "\n",
    "# insert some nodes\n",
    "linked_list.insert_front(35)\n",
    "linked_list.insert_front(35)\n",
    "linked_list.insert_front(37)\n",
    "linked_list.insert_front(37)\n",
    "linked_list.insert_end(90)\n",
    "linked_list.insert_end('Bob')\n",
    "linked_list.insert_end(35)\n",
    "\n",
    "# insert a node inbetween two nodes. First define the node we want to insert the value after\n",
    "second_node = linked_list.head.get_next()\n",
    "\n",
    "# insert the value\n",
    "linked_list.insert_middle(second_node, 50)\n",
    "\n",
    "# traverse our list, to print out the values\n",
    "linked_list.traverse()\n",
    "\n",
    "# grab the last data point\n",
    "linked_list.end.data\n",
    "\n",
    "# determine the size of the linked list\n",
    "linked_list.list_size()\n",
    "\n",
    "# delete a value from the linked list\n",
    "print('-'*50)\n",
    "linked_list.delete_node(90)\n",
    "\n",
    "# traverse our list, to print out the values\n",
    "linked_list.traverse()\n",
    "\n",
    "# search the list for a value\n",
    "linked_list.search_list(20)\n",
    "\n",
    "# remove duplicates\n",
    "linked_list.remove_duplicates()\n",
    "\n",
    "# traverse the list without duplicates\n",
    "print('-'*50)\n",
    "linked_list.traverse()\n",
    "\n",
    "# clear the list\n",
    "linked_list.delete_list()\n",
    "\n",
    "# print out the head, should return an error now.\n",
    "linked_list.head.data\n",
    "\n",
    "print('-'*50)\n",
    "linked_list.kth_to_last(3)\n",
    "\n",
    "linked_list.sum_linked_list(linked_list2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
